/**
 * Design a data structure that follows the constraints of a Least Recently Used (
 * LRU) cache.
 * <p>
 * Implement the LRUCache class:
 * <p>
 * <p>
 * LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
 * int get(int key) Return the value of the key if the key exists, otherwise
 * return -1.
 * void put(int key, int value) Update the value of the key if the key exists.
 * Otherwise, add the key-value pair to the cache. If the number of keys exceeds the
 * capacity from this operation, evict the least recently used key.
 * <p>
 * <p>
 * The functions get and put must each run in O(1) average time complexity.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input
 * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * Output
 * [null, null, null, 1, null, -1, null, -1, 3, 4]
 * <p>
 * Explanation
 * LRUCache lRUCache = new LRUCache(2);
 * lRUCache.put(1, 1); // cache is {1=1}
 * lRUCache.put(2, 2); // cache is {1=1, 2=2}
 * lRUCache.get(1);    // return 1
 * lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
 * lRUCache.get(2);    // returns -1 (not found)
 * lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
 * lRUCache.get(1);    // return -1 (not found)
 * lRUCache.get(3);    // return 3
 * lRUCache.get(4);    // return 4
 * <p>
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= capacity <= 3000
 * 0 <= key <= 10⁴
 * 0 <= value <= 10⁵
 * At most 2 * 10⁵ calls will be made to get and put.
 * <p>
 * <p>
 * Related Topics 设计 哈希表 链表 双向链表 👍 2467 👎 0
 */


package com.xixi.basicAlgroithms.hash;

import java.util.HashMap;
import java.util.Map;

public class ID00146LruCache {
    public static void main(String[] args) {

        LRUCache solution = new ID00146LruCache().new LRUCache(2);

        solution.get(2);
        solution.put(2, 6);
        solution.get(1);
        solution.put(1, 5);
        solution.put(1, 2);
        solution.get(1);
        solution.get(2);


    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class LRUCache {


        int capacity;
        int size;
        ListNode head = new ListNode(-1, -1);
        ListNode tail = new ListNode(-1, -1);

        Map<Integer, ListNode> cache;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.cache = new HashMap<>(capacity);

            head.next = tail;
            tail.previous = head;

        }

        public int get(int key) {
            if (size == 0) return -1;

            if (cache.containsKey(key)) {
                ListNode found = cache.get(key);
                removeNode(found);
                moveNodeToHead(found);
                return found.val;
            } else {
                return -1;
            }

        }

        public void put(int key, int value) {
            ListNode newNode;
            if (cache.containsKey(key)) {
                newNode = cache.get(key);
                newNode.val = value;
                removeNode(newNode);
            } else {
                newNode = new ListNode(key, value);
                size++;
            }
            moveNodeToHead(newNode);
            cache.put(key, newNode);

            if (size > capacity) {
                cache.remove(tail.previous.key);
                removeNode(tail.previous);
                size--;
            }
        }


        public void removeNode(ListNode listNode) {
            listNode.previous.next = listNode.next;
            listNode.next.previous = listNode.previous;
        }

        public void moveNodeToHead(ListNode listNode) {
            listNode.next = head.next;
            listNode.previous = head;
            head.next.previous = listNode;
            head.next = listNode;
        }


        class ListNode {
            public int key;
            public int val;
            public ListNode next;
            public ListNode previous;

            public ListNode() {

            }

            public ListNode(int key, int val) {
                this.key = key;
                this.val = val;
            }

        }
    }

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)


}